Spatially Continuous Data IV

NOTE: You can download the source files for this book from here. The source files are in the format of R Notebooks. Notebooks are pretty neat, because the allow you execute code within the notebook, so that you can work interactively with the notes.

If you wish to work interactively with this chapter you will need the following:

Learning objectives

In the previous practice you were introduced to the concept of variographic analysis for fields/spatially continuous data. In this practice, we will learn:

  1. How to use residual spatial pattern to estimate prediction errors.
  2. Kriging: a method for optimal predictions.

Suggested reading

  • Bailey TC and Gatrell AC [-@Bailey1995] Interactive Spatial Data Analysis, Chapters 5 and 6. Longman: Essex.
  • Bivand RS, Pebesma E, and Gomez-Rubio V [-@Bivand2008] Applied Spatial Data Analysis with R, Chapter 8. Springer: New York.
  • Brunsdon C and Comber L [-@Brunsdon2015R] An Introduction to R for Spatial Analysis and Mapping, Chapter 6, Sections 6.7 and 6.8. Sage: Los Angeles.
  • Isaaks EH and Srivastava RM [-@Isaaks1989applied] An Introduction to Applied Geostatistics, CHAPTERS. Oxford University Press: Oxford.
  • O’Sullivan D and Unwin D [-@Osullivan2010] Geographic Information Analysis, 2nd Edition, Chapters 9 and 10. John Wiley & Sons: New Jersey.

Preliminaries

As usual, it is good practice to clear the working space to make sure that you do not have extraneous items there when you begin your work. The command in R to clear the workspace is rm (for “remove”), followed by a list of items to be removed. To clear the workspace from all objects, do the following:

rm(list = ls())

Note that ls() lists all objects currently on the worspace.

Load the libraries you will use in this activity:

library(tidyverse)
library(spdep)
library(plotly)
library(gstat)
library(geog4ga3)

Begin by loading the data file:

data("Walker_Lake")

You can verify the contents of the dataframe:

summary(Walker_Lake)
      ID                  X               Y               V                U           T      
 Length:470         Min.   :  8.0   Min.   :  8.0   Min.   :   0.0   Min.   :   0.00   1: 45  
 Class :character   1st Qu.: 51.0   1st Qu.: 80.0   1st Qu.: 182.0   1st Qu.:  83.95   2:425  
 Mode  :character   Median : 89.0   Median :139.5   Median : 425.2   Median : 335.00          
                    Mean   :111.1   Mean   :141.3   Mean   : 435.4   Mean   : 613.27          
                    3rd Qu.:170.0   3rd Qu.:208.0   3rd Qu.: 644.4   3rd Qu.: 883.20          
                    Max.   :251.0   Max.   :291.0   Max.   :1528.1   Max.   :5190.10          
                                                                     NA's   :195              

Using residual spatial pattern to estimate prediction errors

Previously, in Chapter @ref{spatially-continuous-data-ii} we discussed how to interpolate a field using trend surface analysis; we also saw how that method may lead to residuals that are not spatially independent.

The implication of non-random residuals is that there is systematic residual pattern that the model did not capture; This, in turn, means that there is at least some information that can still be extracted from the residuals. Again, we will use the case of Walker Lake to explore one way to do this.

As before, we first calculate the polynomial terms of the coordinates to fit a trend surface to the data:

Walker_Lake <- mutate(Walker_Lake,
                        X3 = X^3, X2Y = X^2 * Y, X2 = X^2, 
                        XY = X * Y,
                        Y2 = Y^2, XY2 = X * Y^2, Y3 = Y^3)

Given the polynomial expansion, we can proceed to estimate the following cubic trend surface model, which we already know provided the best fit to the data:

WL.trend3 <- lm(formula = V ~ X3 + X2Y + X2 + X + XY + Y + Y2 + XY2 + Y3, 
                data = Walker_Lake)
summary(WL.trend3)

Call:
lm(formula = V ~ X3 + X2Y + X2 + X + XY + Y + Y2 + XY2 + Y3, 
    data = Walker_Lake)

Residuals:
    Min      1Q  Median      3Q     Max 
-564.19 -197.41    7.91  194.25  929.72 

Coefficients:
              Estimate Std. Error t value Pr(>|t|)    
(Intercept) -8.620e+00  1.227e+02  -0.070 0.944035    
X3           1.533e-04  4.806e-05   3.190 0.001522 ** 
X2Y          6.139e-05  3.909e-05   1.570 0.117000    
X2          -6.651e-02  1.838e-02  -3.618 0.000330 ***
X            9.172e+00  2.386e+00   3.844 0.000138 ***
XY          -4.420e-02  1.430e-02  -3.092 0.002110 ** 
Y            4.794e+00  2.040e+00   2.350 0.019220 *  
Y2          -1.806e-03  1.327e-02  -0.136 0.891822    
XY2          7.679e-05  2.956e-05   2.598 0.009669 ** 
Y3          -4.170e-05  2.819e-05  -1.479 0.139759    
---
Signif. codes:  0 ‘***’ 0.001 ‘**’ 0.01 ‘*’ 0.05 ‘.’ 0.1 ‘ ’ 1

Residual standard error: 276.7 on 460 degrees of freedom
Multiple R-squared:  0.1719,    Adjusted R-squared:  0.1557 
F-statistic: 10.61 on 9 and 460 DF,  p-value: 5.381e-15

We can next visualize the residuals which, as you can see, do not appear to be random

plot_ly(x = ~Walker_Lake$X, y = ~Walker_Lake$Y, z = ~WL.trend3$residuals, color = ~WL.trend3$residuals < 0, colors = c("blue", "red"), type = "scatter3d")
No scatter3d mode specifed:
  Setting the mode to markers
  Read more about this attribute -> https://plot.ly/r/reference/#scatter-mode
No scatter3d mode specifed:
  Setting the mode to markers
  Read more about this attribute -> https://plot.ly/r/reference/#scatter-mode

Now we will create an interpolation grid:

# The function `sequence()` create a sequence of values from - to using by as the step increment. In this case, we generate a grid with points that are 2.5 m apart.
X.p <- seq(from = 0.1, to = 255.1, by = 2.5)
Y.p <- seq(from = 0.1, to = 295.1, by = 2.5)
df.p <- expand.grid(X = X.p, Y = Y.p)

WE can add the polynomial terms to this grid. Since our trend surface model was estimated using the cubic polynomial, we add those terms to the dataframe:

df.p <- mutate(df.p, X3 = X^3, X2Y = X^2 * Y, X2 = X^2, 
               XY = X * Y, 
               Y2 = Y^2, XY2 = X * Y^2, Y3 = Y^3)

The interpolated cubic surface is obtained by using the model and the interpolation grid as newdata:

# The function `predict()` is used to make predictions given a model and a possibly new dataset, different from the one used for estimation of the model.
WL.preds3 <- predict(WL.trend3, newdata = df.p, se.fit = TRUE, interval = "prediction", level = 0.95)

The surface is converted into a matrix for 3D plotting:

z.p3 <- matrix(data = WL.preds3$fit[,1], nrow = length(Y.p), ncol = length(X.p), byrow = TRUE)

And plot:

WL.plot3 <- plot_ly(x = ~X.p, y = ~Y.p, z = ~z.p3, 
        type = "surface", colors = "YlOrRd") %>% 
  layout(scene = list(
    aspectmode = "manual", aspectratio = list(x = 1, y = 1, z = 1)))
WL.plot3

The trend surface provides a smooth estimate of the field. However, it is not sufficient to capture all systematic variation, and fails to produce random residuals.

A possible way of enhancing this approach to interpolation is to exploit the information that remains in the residuals, for instance by the use of \(k\)-point means.

We can illustrate this as follows. To interpolate the residuals, we first need the set of target points (the points for the interpolation), as well as the source (the observations):

target_xy = expand.grid(x = X.p, y = Y.p)
source_xy = cbind(x = Walker_Lake$X, y = Walker_Lake$Y)

It is possible now to use the kpointmean function to interpolate the residuals, for instance using \(k=5\) neighbors:

kpoint.5 <- kpointmean(source_xy = source_xy, z = WL.trend3$residuals, target_xy = target_xy, k = 5)

Given the interpolated residuals, we can join them to the cubic trend surface, as follows:

z.p3 <- matrix(data = WL.preds3$fit[,1] + kpoint.5$z,
               nrow = length(Y.p), ncol = length(X.p), byrow = TRUE)

This is now the interpolated field that combines the trend surface and the estimated residuals:

WL.plot3 <- plot_ly(x = ~X.p, y = ~Y.p, z = ~z.p3, 
        type = "surface", colors = "YlOrRd") %>% 
  layout(scene = list(
    aspectmode = "manual", aspectratio = list(x = 1, y = 1, z = 1)))
WL.plot3

Of all the approaches that we have seen so far, this is the first that provides a genuine estimate of the following: \[ \hat{z}_p + \hat{\epsilon}_p \]

With trend surface analysis providing a smooth estimator of the underlying field: \[ \hat{z}_p = f(x_p, y_p) \]

And \(k\)-point means providing an estimator of: \[ \hat{\epsilon}_p \]

A question is how to decide the number of neighbors to use in the calculation of the \(k\)-point means. As previously discussed, \(k\)=1 becomes identical to Voronoi polygons, and \(k = n\) becomes the global mean.

A second question concerns the way the average is calculated. As variographic analysis demonstrates, it is possible to estimate the way in which spatial dependence weakens with distance. Why should more distant points be weighted equally? The answer is, there is no reason why they should, and in fact, variographic analysis elegantly solves this, as well the question of how many points to use: all of them, with varying weights.

Next, we will introduce kriging, a method for optimal prediction that is based on the use of variographic analyisis.

Kriging: a method for optimal prediction.

To introduce the method known as kriging, we will begin by positing a situation as follows:

\[ \hat{z}_p + \hat{\epsilon}_p = \hat{f}(x_p, y_p) + \hat{\epsilon}_p \]

where \(\hat{f}(x_p, y_p)\) is a smooth estimator of an underlying field.

We aim to predict \(\hat{\epsilon}_p\) based on the observed residuals. We use an expression similar to the one used for IDW and \(k\)-point means in Chapter @ref{spatially-continuous-data-i} (we will use \(\lambda\) for the weights to avoid confusing the the weights in variographic analysis):

\[ \hat{\epsilon}_p = \sum_{i=1}^n {\lambda_{pi}\epsilon_i} \]

That is, \(\hat{\epsilon}_p\) is a linear combination of the prediction residuals from the trend: \[ \epsilon_i = z_i - \hat{f}(x_i, y_i) \]

It is possible to define the following expected mean squared error, or prediction variance: \[ \sigma_{\epsilon}^2 = E[(\hat{\epsilon}_p - \epsilon_i)^2] \]

The prediction variance measures how close, on average, the prediction error is to the residuals.

The prediction variance can be decomposed as follows: \[ \sigma_{\epsilon}^2 = E[\hat{\epsilon}_p] + E[\epsilon_i] - 2E[\hat{\epsilon_i\epsilon}_p] \]

It turns out (we will not show de detailed derivation, but it can be consulted here), that the expresion for the prediction variance depends on the weights: \[ \sigma_{\epsilon}^2 = \sum_{i=1}^n \sum_{j=1}^n{\lambda_{ip}\lambda_{jp}C_{ij}} + \sigma^2 + 2\sum_{i=1}^{n}{\lambda_{ip}C_{ip}} \] where \(C_{ij}\) is the autocovariance between observations at \(i\) and \(j\), and \(C_{ip}\) is the autocovariance between the observation at \(i\) and prediction location \(p\).

Fortunately for us, the semivariogram and the autocovariance is straightforward: \[ C_{z}(h) =\sigma^2 - \hat{\gamma}_{z}(h) \]

This means that, given the distance \(h\) between \(i\) and \(j\), and \(i\) and \(p\), we can use a semivariogram to obtain the autocovariances needed to calculate the prediction variance. We are still missing, however, the weights \(\lambda\), which are not known a priori.

These weights can be obtained if we use the following rules:

The expectation of the prediction errors is zero (unbiassedness) Find the weights \(lambda\) that minimize the prediction variance (optimal estimator).

This makes sense, since we would like our predictions to be unbiased (i.e., accurate) and as precise as possible, that is, to have the smallest variance (recall the discussion about accuracy and precision in Chapter @ref{spatially-continuous-data-iii}).

Again, solving the minimization problem is beyond the scope of our presentation, but it suffices to say that the result is as follows:

\[ \mathbf{\lambda}_p = \mathbf{C}^{-1}\mathit{c}_{p} \]

where \(\mathbf{C}\) is the covariance matrix, and \(\mathit{c}_{p}\) is the covariance vector for location \(p\).

In summary, kriging is a method to optimally estimate the value of a variable at \(p\) as a weighted sum of the observations of the same variable at locations \(i\). This method is known to have the properties of Best (in the sense that it minimizes the variance) Linear (because predictions are a linear combination of weights) Unbiased (since the estimators of the prediction errors are zero) Predictor, or BLUP.

Kriging is implemented in the package gstat as follows.

To put kriging to work we must first conduct variographic analysis of the residuals. The function variogram uses as an argument a simple features object that we can create as follows:

Walker_Lake.sf <- Walker_Lake %>%
  st_as_sf(coords = c("X", "Y"),
           remove = FALSE) # Remove false to retain the X and Y coordinates in the dataframe after they are converted to simple features

The variogram of the residuals can be obtained by specifying a trend surface in the formula:

variogram_v <- variogram(V ~ X3 + X2Y + X2 + X + XY + Y + Y2 + XY2 + Y3, 
                         data = Walker_Lake.sf)
ggplot(data = variogram_v, aes(x = dist, y = gamma)) +
  geom_point() + 
  geom_text(aes(label = np), nudge_y = -1500) + # Nudge the labels away from the points
  xlab("Distance") + ylab("Semivariance")

You can verify that the semivariogram above corresponds to the residuals by repeating the analysis directly on the residuals. First join the residuals to the SpatialPointsDataFrame:

Walker_Lake.sf$e <- WL.trend3$residuals

And then calculate the semivariogram and plot:

variogram_e <- variogram(e ~ 1, 
                         data = Walker_Lake.sf)
ggplot(data = variogram_e, aes(x = dist, y = gamma)) +
  geom_point() + 
  geom_text(aes(label = np), nudge_y = -1500) +
  xlab("Distance") + ylab("Semivariance")

The empirical semivariogram is used to estimate a semivariogram function:

variogram_v.t <- fit.variogram(variogram_v, model = vgm("Exp", "Sph", "Gau"))
variogram_v.t

The variogram function plots as follows:

gamma.t <- variogramLine(variogram_v.t, maxdist = 130)
ggplot(data = variogram_v, aes(x = dist, y = gamma)) +
  geom_point(size = 3) + 
  geom_line(data = gamma.t, aes(x = dist, y = gamma)) +
  xlab("Distance") + ylab("Semivariance")

We will convert the prediction grid to a simple features object:

df.sf <- df.p %>%
  st_as_sf(coords = c("X", "Y"),
           remove = FALSE)
#coordinates(df.sp) <- ~X+Y

Then, we can krige the field as follows (ensure that packages sf and stars are installed):

V.kriged <- krige(V ~ X3 + X2Y + X2 + X + XY + Y + Y2 + XY2 + Y3,
              Walker_Lake.sf, df.sf, variogram_v.t)
[using universal kriging]

Extract the predictions and prediction variance from the object V.kriged:

V.km <- matrix(data = V.kriged$var1.pred,
               nrow = 119, ncol = 103, byrow = TRUE)
V.sm <- matrix(data = V.kriged$var1.var,
               nrow = 119, ncol = 103, byrow = TRUE)

We can now plot the interpolated field:

V.km.plot <- plot_ly(x = ~X.p, y = ~Y.p, z = ~V.km, 
        type = "surface", colors = "YlOrRd") %>% 
  layout(scene = list(
    aspectmode = "manual", aspectratio = list(x = 1, y = 1, z = 1)))
V.km.plot

Also, we can plot the kriging standard errors (the square root of the prediction variance). This gives an estimate of the uncertainty in the predictions:

V.sm.plot <- plot_ly(x = ~X.p, y = ~Y.p, z = ~sqrt(V.sm), 
        type = "surface", colors = "YlOrRd") %>% 
  layout(scene = list(
    aspectmode = "manual", aspectratio = list(x = 1, y = 1, z = 1)))
V.sm.plot

Where are predictions more/less precise?

LS0tDQp0aXRsZTogIlNwYXRpYWxseSBDb250aW51b3VzIERhdGEgSVYiDQpvdXRwdXQ6IGh0bWxfbm90ZWJvb2sNCi0tLQ0KDQojIFNwYXRpYWxseSBDb250aW51b3VzIERhdGEgSVYNCg0KKk5PVEUqOiBZb3UgY2FuIGRvd25sb2FkIHRoZSBzb3VyY2UgZmlsZXMgZm9yIHRoaXMgYm9vayBmcm9tIFtoZXJlXShodHRwczovL2dpdGh1Yi5jb20vcGFlemhhL1NwYXRpYWwtU3RhdGlzdGljcy1Db3Vyc2UpLiBUaGUgc291cmNlIGZpbGVzIGFyZSBpbiB0aGUgZm9ybWF0IG9mIFIgTm90ZWJvb2tzLiBOb3RlYm9va3MgYXJlIHByZXR0eSBuZWF0LCBiZWNhdXNlIHRoZSBhbGxvdyB5b3UgZXhlY3V0ZSBjb2RlIHdpdGhpbiB0aGUgbm90ZWJvb2ssIHNvIHRoYXQgeW91IGNhbiB3b3JrIGludGVyYWN0aXZlbHkgd2l0aCB0aGUgbm90ZXMuIA0KDQpJZiB5b3Ugd2lzaCB0byB3b3JrIGludGVyYWN0aXZlbHkgd2l0aCB0aGlzIGNoYXB0ZXIgeW91IHdpbGwgbmVlZCB0aGUgZm9sbG93aW5nOg0KDQoqIEFuIFIgbWFya2Rvd24gbm90ZWJvb2sgdmVyc2lvbiBvZiB0aGlzIGRvY3VtZW50ICh0aGUgc291cmNlIGZpbGUpLg0KDQoqIEEgcGFja2FnZSBjYWxsZWQgYGdlb2c0Z2EzYC4NCg0KIyMgTGVhcm5pbmcgb2JqZWN0aXZlcw0KDQpJbiB0aGUgcHJldmlvdXMgcHJhY3RpY2UgeW91IHdlcmUgaW50cm9kdWNlZCB0byB0aGUgY29uY2VwdCBvZiB2YXJpb2dyYXBoaWMgYW5hbHlzaXMgZm9yIGZpZWxkcy9zcGF0aWFsbHkgY29udGludW91cyBkYXRhLiBJbiB0aGlzIHByYWN0aWNlLCB3ZSB3aWxsIGxlYXJuOg0KDQoxLiBIb3cgdG8gdXNlIHJlc2lkdWFsIHNwYXRpYWwgcGF0dGVybiB0byBlc3RpbWF0ZSBwcmVkaWN0aW9uIGVycm9ycy4NCjIuIEtyaWdpbmc6IGEgbWV0aG9kIGZvciBvcHRpbWFsIHByZWRpY3Rpb25zLg0KDQojIyBTdWdnZXN0ZWQgcmVhZGluZw0KDQotIEJhaWxleSBUQyBhbmQgR2F0cmVsbCBBQyBbLUBCYWlsZXkxOTk1XSBJbnRlcmFjdGl2ZSBTcGF0aWFsIERhdGEgQW5hbHlzaXMsIENoYXB0ZXJzIDUgYW5kIDYuIExvbmdtYW46IEVzc2V4Lg0KLSBCaXZhbmQgUlMsIFBlYmVzbWEgRSwgYW5kIEdvbWV6LVJ1YmlvIFYgWy1AQml2YW5kMjAwOF0gQXBwbGllZCBTcGF0aWFsIERhdGEgQW5hbHlzaXMgd2l0aCBSLCBDaGFwdGVyIDguIFNwcmluZ2VyOiBOZXcgWW9yay4NCi0gQnJ1bnNkb24gQyBhbmQgQ29tYmVyIEwgWy1AQnJ1bnNkb24yMDE1Ul0gQW4gSW50cm9kdWN0aW9uIHRvIFIgZm9yIFNwYXRpYWwgQW5hbHlzaXMgYW5kIE1hcHBpbmcsIENoYXB0ZXIgNiwgU2VjdGlvbnMgNi43IGFuZCA2LjguIFNhZ2U6IExvcyBBbmdlbGVzLg0KLSBJc2Fha3MgRUggYW5kIFNyaXZhc3RhdmEgUk0gIFstQElzYWFrczE5ODlhcHBsaWVkXSBBbiBJbnRyb2R1Y3Rpb24gdG8gQXBwbGllZCBHZW9zdGF0aXN0aWNzLCAqKkNIQVBURVJTKiouIE94Zm9yZCBVbml2ZXJzaXR5IFByZXNzOiBPeGZvcmQuDQotIE8nU3VsbGl2YW4gRCBhbmQgVW53aW4gRCBbLUBPc3VsbGl2YW4yMDEwXSBHZW9ncmFwaGljIEluZm9ybWF0aW9uIEFuYWx5c2lzLCAybmQgRWRpdGlvbiwgQ2hhcHRlcnMgOSBhbmQgMTAuIEpvaG4gV2lsZXkgJiBTb25zOiBOZXcgSmVyc2V5Lg0KDQojIyBQcmVsaW1pbmFyaWVzDQoNCkFzIHVzdWFsLCBpdCBpcyBnb29kIHByYWN0aWNlIHRvIGNsZWFyIHRoZSB3b3JraW5nIHNwYWNlIHRvIG1ha2Ugc3VyZSB0aGF0IHlvdSBkbyBub3QgaGF2ZSBleHRyYW5lb3VzIGl0ZW1zIHRoZXJlIHdoZW4geW91IGJlZ2luIHlvdXIgd29yay4gVGhlIGNvbW1hbmQgaW4gYFJgIHRvIGNsZWFyIHRoZSB3b3Jrc3BhY2UgaXMgYHJtYCAoZm9yICJyZW1vdmUiKSwgZm9sbG93ZWQgYnkgYSBsaXN0IG9mIGl0ZW1zIHRvIGJlIHJlbW92ZWQuIFRvIGNsZWFyIHRoZSB3b3Jrc3BhY2UgZnJvbSBfYWxsXyBvYmplY3RzLCBkbyB0aGUgZm9sbG93aW5nOg0KYGBge3J9DQpybShsaXN0ID0gbHMoKSkNCmBgYA0KDQpOb3RlIHRoYXQgYGxzKClgIGxpc3RzIGFsbCBvYmplY3RzIGN1cnJlbnRseSBvbiB0aGUgd29yc3BhY2UuDQoNCkxvYWQgdGhlIGxpYnJhcmllcyB5b3Ugd2lsbCB1c2UgaW4gdGhpcyBhY3Rpdml0eToNCmBgYHtyIG1lc3NhZ2U9RkFMU0UsIHdhcm5pbmc9RkFMU0V9DQpsaWJyYXJ5KHRpZHl2ZXJzZSkNCmxpYnJhcnkoc3BkZXApDQpsaWJyYXJ5KHBsb3RseSkNCmxpYnJhcnkoZ3N0YXQpDQpsaWJyYXJ5KGdlb2c0Z2EzKQ0KYGBgDQoNCkJlZ2luIGJ5IGxvYWRpbmcgdGhlIGRhdGEgZmlsZToNCmBgYHtyfQ0KZGF0YSgiV2Fsa2VyX0xha2UiKQ0KYGBgDQoNCllvdSBjYW4gdmVyaWZ5IHRoZSBjb250ZW50cyBvZiB0aGUgZGF0YWZyYW1lOg0KYGBge3J9DQpzdW1tYXJ5KFdhbGtlcl9MYWtlKQ0KYGBgDQoNCiMjIFVzaW5nIHJlc2lkdWFsIHNwYXRpYWwgcGF0dGVybiB0byBlc3RpbWF0ZSBwcmVkaWN0aW9uIGVycm9ycw0KDQpQcmV2aW91c2x5LCBpbiBDaGFwdGVyIFxAcmVme3NwYXRpYWxseS1jb250aW51b3VzLWRhdGEtaWl9IHdlIGRpc2N1c3NlZCBob3cgdG8gaW50ZXJwb2xhdGUgYSBmaWVsZCB1c2luZyB0cmVuZCBzdXJmYWNlIGFuYWx5c2lzOyB3ZSBhbHNvIHNhdyBob3cgdGhhdCBtZXRob2QgbWF5IGxlYWQgdG8gcmVzaWR1YWxzIHRoYXQgYXJlIG5vdCBzcGF0aWFsbHkgaW5kZXBlbmRlbnQuIA0KDQpUaGUgaW1wbGljYXRpb24gb2Ygbm9uLXJhbmRvbSByZXNpZHVhbHMgaXMgdGhhdCB0aGVyZSBpcyBzeXN0ZW1hdGljIHJlc2lkdWFsIHBhdHRlcm4gdGhhdCB0aGUgbW9kZWwgZGlkIG5vdCBjYXB0dXJlOyBUaGlzLCBpbiB0dXJuLCBtZWFucyB0aGF0IHRoZXJlIGlzIGF0IGxlYXN0IF9zb21lXyBpbmZvcm1hdGlvbiB0aGF0IGNhbiBzdGlsbCBiZSBleHRyYWN0ZWQgZnJvbSB0aGUgcmVzaWR1YWxzLiBBZ2Fpbiwgd2Ugd2lsbCB1c2UgdGhlIGNhc2Ugb2YgV2Fsa2VyIExha2UgdG8gZXhwbG9yZSBvbmUgd2F5IHRvIGRvIHRoaXMuDQoNCkFzIGJlZm9yZSwgd2UgZmlyc3QgY2FsY3VsYXRlIHRoZSBwb2x5bm9taWFsIHRlcm1zIG9mIHRoZSBjb29yZGluYXRlcyB0byBmaXQgYSB0cmVuZCBzdXJmYWNlIHRvIHRoZSBkYXRhOg0KYGBge3J9DQpXYWxrZXJfTGFrZSA8LSBtdXRhdGUoV2Fsa2VyX0xha2UsDQogICAgICAgICAgICAgICAgICAgICAgICBYMyA9IFheMywgWDJZID0gWF4yICogWSwgWDIgPSBYXjIsIA0KICAgICAgICAgICAgICAgICAgICAgICAgWFkgPSBYICogWSwNCiAgICAgICAgICAgICAgICAgICAgICAgIFkyID0gWV4yLCBYWTIgPSBYICogWV4yLCBZMyA9IFleMykNCmBgYA0KDQpHaXZlbiB0aGUgcG9seW5vbWlhbCBleHBhbnNpb24sIHdlIGNhbiBwcm9jZWVkIHRvIGVzdGltYXRlIHRoZSBmb2xsb3dpbmcgY3ViaWMgdHJlbmQgc3VyZmFjZSBtb2RlbCwgd2hpY2ggd2UgYWxyZWFkeSBrbm93IHByb3ZpZGVkIHRoZSBiZXN0IGZpdCB0byB0aGUgZGF0YToNCmBgYHtyfQ0KV0wudHJlbmQzIDwtIGxtKGZvcm11bGEgPSBWIH4gWDMgKyBYMlkgKyBYMiArIFggKyBYWSArIFkgKyBZMiArIFhZMiArIFkzLCANCiAgICAgICAgICAgICAgICBkYXRhID0gV2Fsa2VyX0xha2UpDQpzdW1tYXJ5KFdMLnRyZW5kMykNCmBgYA0KDQpXZSBjYW4gbmV4dCB2aXN1YWxpemUgdGhlIHJlc2lkdWFscyB3aGljaCwgYXMgeW91IGNhbiBzZWUsIGRvIG5vdCBhcHBlYXIgdG8gYmUgcmFuZG9tIA0KYGBge3J9DQpwbG90X2x5KHggPSB+V2Fsa2VyX0xha2UkWCwgeSA9IH5XYWxrZXJfTGFrZSRZLCB6ID0gfldMLnRyZW5kMyRyZXNpZHVhbHMsIGNvbG9yID0gfldMLnRyZW5kMyRyZXNpZHVhbHMgPCAwLCBjb2xvcnMgPSBjKCJibHVlIiwgInJlZCIpLCB0eXBlID0gInNjYXR0ZXIzZCIpDQpgYGANCg0KTm93IHdlIHdpbGwgY3JlYXRlIGFuIGludGVycG9sYXRpb24gZ3JpZDoNCmBgYHtyfQ0KIyBUaGUgZnVuY3Rpb24gYHNlcXVlbmNlKClgIGNyZWF0ZSBhIHNlcXVlbmNlIG9mIHZhbHVlcyBmcm9tIC0gdG8gdXNpbmcgYnkgYXMgdGhlIHN0ZXAgaW5jcmVtZW50LiBJbiB0aGlzIGNhc2UsIHdlIGdlbmVyYXRlIGEgZ3JpZCB3aXRoIHBvaW50cyB0aGF0IGFyZSAyLjUgbSBhcGFydC4NClgucCA8LSBzZXEoZnJvbSA9IDAuMSwgdG8gPSAyNTUuMSwgYnkgPSAyLjUpDQpZLnAgPC0gc2VxKGZyb20gPSAwLjEsIHRvID0gMjk1LjEsIGJ5ID0gMi41KQ0KZGYucCA8LSBleHBhbmQuZ3JpZChYID0gWC5wLCBZID0gWS5wKQ0KYGBgDQoNCldFIGNhbiBhZGQgdGhlIHBvbHlub21pYWwgdGVybXMgdG8gdGhpcyBncmlkLiBTaW5jZSBvdXIgdHJlbmQgc3VyZmFjZSBtb2RlbCB3YXMgZXN0aW1hdGVkIHVzaW5nIHRoZSBjdWJpYyBwb2x5bm9taWFsLCB3ZSBhZGQgdGhvc2UgdGVybXMgdG8gdGhlIGRhdGFmcmFtZToNCmBgYHtyfQ0KZGYucCA8LSBtdXRhdGUoZGYucCwgWDMgPSBYXjMsIFgyWSA9IFheMiAqIFksIFgyID0gWF4yLCANCiAgICAgICAgICAgICAgIFhZID0gWCAqIFksIA0KICAgICAgICAgICAgICAgWTIgPSBZXjIsIFhZMiA9IFggKiBZXjIsIFkzID0gWV4zKQ0KYGBgDQoNClRoZSBpbnRlcnBvbGF0ZWQgY3ViaWMgc3VyZmFjZSBpcyBvYnRhaW5lZCBieSB1c2luZyB0aGUgbW9kZWwgYW5kIHRoZSBpbnRlcnBvbGF0aW9uIGdyaWQgYXMgYG5ld2RhdGFgOg0KYGBge3J9DQojIFRoZSBmdW5jdGlvbiBgcHJlZGljdCgpYCBpcyB1c2VkIHRvIG1ha2UgcHJlZGljdGlvbnMgZ2l2ZW4gYSBtb2RlbCBhbmQgYSBwb3NzaWJseSBuZXcgZGF0YXNldCwgZGlmZmVyZW50IGZyb20gdGhlIG9uZSB1c2VkIGZvciBlc3RpbWF0aW9uIG9mIHRoZSBtb2RlbC4NCldMLnByZWRzMyA8LSBwcmVkaWN0KFdMLnRyZW5kMywgbmV3ZGF0YSA9IGRmLnAsIHNlLmZpdCA9IFRSVUUsIGludGVydmFsID0gInByZWRpY3Rpb24iLCBsZXZlbCA9IDAuOTUpDQpgYGANCg0KVGhlIHN1cmZhY2UgaXMgY29udmVydGVkIGludG8gYSBtYXRyaXggZm9yIDNEIHBsb3R0aW5nOg0KYGBge3J9DQp6LnAzIDwtIG1hdHJpeChkYXRhID0gV0wucHJlZHMzJGZpdFssMV0sIG5yb3cgPSBsZW5ndGgoWS5wKSwgbmNvbCA9IGxlbmd0aChYLnApLCBieXJvdyA9IFRSVUUpDQpgYGANCg0KQW5kIHBsb3Q6DQpgYGB7cn0NCldMLnBsb3QzIDwtIHBsb3RfbHkoeCA9IH5YLnAsIHkgPSB+WS5wLCB6ID0gfnoucDMsIA0KICAgICAgICB0eXBlID0gInN1cmZhY2UiLCBjb2xvcnMgPSAiWWxPclJkIikgJT4lIA0KICBsYXlvdXQoc2NlbmUgPSBsaXN0KA0KICAgIGFzcGVjdG1vZGUgPSAibWFudWFsIiwgYXNwZWN0cmF0aW8gPSBsaXN0KHggPSAxLCB5ID0gMSwgeiA9IDEpKSkNCldMLnBsb3QzDQpgYGANCg0KVGhlIHRyZW5kIHN1cmZhY2UgcHJvdmlkZXMgYSBzbW9vdGggZXN0aW1hdGUgb2YgdGhlIGZpZWxkLiBIb3dldmVyLCBpdCBpcyBub3Qgc3VmZmljaWVudCB0byBjYXB0dXJlIGFsbCBzeXN0ZW1hdGljIHZhcmlhdGlvbiwgYW5kIGZhaWxzIHRvIHByb2R1Y2UgcmFuZG9tIHJlc2lkdWFscy4NCg0KQSBwb3NzaWJsZSB3YXkgb2YgZW5oYW5jaW5nIHRoaXMgYXBwcm9hY2ggdG8gaW50ZXJwb2xhdGlvbiBpcyB0byBfZXhwbG9pdF8gdGhlIGluZm9ybWF0aW9uIHRoYXQgcmVtYWlucyBpbiB0aGUgcmVzaWR1YWxzLCBmb3IgaW5zdGFuY2UgYnkgdGhlIHVzZSBvZiAkayQtcG9pbnQgbWVhbnMuDQoNCldlICBjYW4gaWxsdXN0cmF0ZSB0aGlzIGFzIGZvbGxvd3MuIFRvIGludGVycG9sYXRlIHRoZSBfcmVzaWR1YWxzXywgd2UgZmlyc3QgbmVlZCB0aGUgc2V0IG9mIF90YXJnZXRfIHBvaW50cyAodGhlIHBvaW50cyBmb3IgdGhlIGludGVycG9sYXRpb24pLCBhcyB3ZWxsIGFzIHRoZSBfc291cmNlXyAodGhlIG9ic2VydmF0aW9ucyk6DQpgYGB7cn0NCiMgV2Ugd2lsbCB1c2UgdGhlIHByZWRpY3Rpb24gZ3JpZCB3ZSB1c2VkIGFib3ZlIHRvIGludGVycG9sYXRlIHRoZSByZXNpZHVhbHMgDQp0YXJnZXRfeHkgPSBleHBhbmQuZ3JpZCh4ID0gWC5wLCB5ID0gWS5wKQ0Kc291cmNlX3h5ID0gY2JpbmQoeCA9IFdhbGtlcl9MYWtlJFgsIHkgPSBXYWxrZXJfTGFrZSRZKQ0KYGBgDQoNCkl0IGlzIHBvc3NpYmxlIG5vdyB0byB1c2UgdGhlIGBrcG9pbnRtZWFuYCBmdW5jdGlvbiB0byBpbnRlcnBvbGF0ZSB0aGUgcmVzaWR1YWxzLCBmb3IgaW5zdGFuY2UgdXNpbmcgJGs9NSQgbmVpZ2hib3JzOg0KYGBge3J9DQprcG9pbnQuNSA8LSBrcG9pbnRtZWFuKHNvdXJjZV94eSA9IHNvdXJjZV94eSwgeiA9IFdMLnRyZW5kMyRyZXNpZHVhbHMsIHRhcmdldF94eSA9IHRhcmdldF94eSwgayA9IDUpDQpgYGANCg0KR2l2ZW4gdGhlIGludGVycG9sYXRlZCByZXNpZHVhbHMsIHdlIGNhbiBqb2luIHRoZW0gdG8gdGhlIGN1YmljIHRyZW5kIHN1cmZhY2UsIGFzIGZvbGxvd3M6DQpgYGB7cn0NCnoucDMgPC0gbWF0cml4KGRhdGEgPSBXTC5wcmVkczMkZml0WywxXSArIGtwb2ludC41JHosDQogICAgICAgICAgICAgICBucm93ID0gbGVuZ3RoKFkucCksIG5jb2wgPSBsZW5ndGgoWC5wKSwgYnlyb3cgPSBUUlVFKQ0KYGBgDQoNClRoaXMgaXMgbm93IHRoZSBpbnRlcnBvbGF0ZWQgZmllbGQgdGhhdCBjb21iaW5lcyB0aGUgdHJlbmQgc3VyZmFjZSBhbmQgdGhlIGVzdGltYXRlZCByZXNpZHVhbHM6DQpgYGB7cn0NCldMLnBsb3QzIDwtIHBsb3RfbHkoeCA9IH5YLnAsIHkgPSB+WS5wLCB6ID0gfnoucDMsIA0KICAgICAgICB0eXBlID0gInN1cmZhY2UiLCBjb2xvcnMgPSAiWWxPclJkIikgJT4lIA0KICBsYXlvdXQoc2NlbmUgPSBsaXN0KA0KICAgIGFzcGVjdG1vZGUgPSAibWFudWFsIiwgYXNwZWN0cmF0aW8gPSBsaXN0KHggPSAxLCB5ID0gMSwgeiA9IDEpKSkNCldMLnBsb3QzDQpgYGANCg0KT2YgYWxsIHRoZSBhcHByb2FjaGVzIHRoYXQgd2UgaGF2ZSBzZWVuIHNvIGZhciwgdGhpcyBpcyB0aGUgZmlyc3QgdGhhdCBwcm92aWRlcyBhIGdlbnVpbmUgZXN0aW1hdGUgb2YgdGhlIGZvbGxvd2luZzoNCiQkDQpcaGF0e3p9X3AgKyBcaGF0e1xlcHNpbG9ufV9wDQokJA0KDQpXaXRoIHRyZW5kIHN1cmZhY2UgYW5hbHlzaXMgcHJvdmlkaW5nIGEgc21vb3RoIGVzdGltYXRvciBvZiB0aGUgdW5kZXJseWluZyBmaWVsZDoNCiQkDQpcaGF0e3p9X3AgPSBmKHhfcCwgeV9wKQ0KJCQNCg0KQW5kICRrJC1wb2ludCBtZWFucyBwcm92aWRpbmcgYW4gZXN0aW1hdG9yIG9mOg0KJCQNClxoYXR7XGVwc2lsb259X3ANCiQkDQoNCkEgcXVlc3Rpb24gaXMgaG93IHRvIGRlY2lkZSB0aGUgbnVtYmVyIG9mIG5laWdoYm9ycyB0byB1c2UgaW4gdGhlIGNhbGN1bGF0aW9uIG9mIHRoZSAkayQtcG9pbnQgbWVhbnMuIEFzIHByZXZpb3VzbHkgZGlzY3Vzc2VkLCAkayQ9MSBiZWNvbWVzIGlkZW50aWNhbCB0byBWb3Jvbm9pIHBvbHlnb25zLCBhbmQgJGsgPSBuJCBiZWNvbWVzIHRoZSBnbG9iYWwgbWVhbi4NCg0KQSBzZWNvbmQgcXVlc3Rpb24gY29uY2VybnMgdGhlIHdheSB0aGUgYXZlcmFnZSBpcyBjYWxjdWxhdGVkLiBBcyB2YXJpb2dyYXBoaWMgYW5hbHlzaXMgZGVtb25zdHJhdGVzLCBpdCBpcyBwb3NzaWJsZSB0byBlc3RpbWF0ZSB0aGUgd2F5IGluIHdoaWNoIHNwYXRpYWwgZGVwZW5kZW5jZSB3ZWFrZW5zIHdpdGggZGlzdGFuY2UuIFdoeSBzaG91bGQgbW9yZSBkaXN0YW50IHBvaW50cyBiZSB3ZWlnaHRlZCBlcXVhbGx5PyBUaGUgYW5zd2VyIGlzLCB0aGVyZSBpcyBubyByZWFzb24gd2h5IHRoZXkgc2hvdWxkLCBhbmQgaW4gZmFjdCwgdmFyaW9ncmFwaGljIGFuYWx5c2lzIGVsZWdhbnRseSBzb2x2ZXMgdGhpcywgYXMgd2VsbCB0aGUgcXVlc3Rpb24gb2YgaG93IG1hbnkgcG9pbnRzIHRvIHVzZTogYWxsIG9mIHRoZW0sIHdpdGggdmFyeWluZyB3ZWlnaHRzLg0KDQpOZXh0LCB3ZSB3aWxsIGludHJvZHVjZSBrcmlnaW5nLCBhIG1ldGhvZCBmb3Igb3B0aW1hbCBwcmVkaWN0aW9uIHRoYXQgaXMgYmFzZWQgb24gdGhlIHVzZSBvZiB2YXJpb2dyYXBoaWMgYW5hbHlpc2lzLg0KDQojIyBLcmlnaW5nOiBhIG1ldGhvZCBmb3Igb3B0aW1hbCBwcmVkaWN0aW9uLg0KDQpUbyBpbnRyb2R1Y2UgdGhlIG1ldGhvZCBrbm93biBhcyBrcmlnaW5nLCB3ZSB3aWxsIGJlZ2luIGJ5IHBvc2l0aW5nIGEgc2l0dWF0aW9uIGFzIGZvbGxvd3M6DQoNCiQkDQpcaGF0e3p9X3AgKyBcaGF0e1xlcHNpbG9ufV9wID0gXGhhdHtmfSh4X3AsIHlfcCkgKyBcaGF0e1xlcHNpbG9ufV9wDQokJA0KDQp3aGVyZSAkXGhhdHtmfSh4X3AsIHlfcCkkIGlzIGEgc21vb3RoIGVzdGltYXRvciBvZiBhbiB1bmRlcmx5aW5nIGZpZWxkLg0KDQpXZSBhaW0gdG8gcHJlZGljdCAkXGhhdHtcZXBzaWxvbn1fcCQgYmFzZWQgb24gdGhlIG9ic2VydmVkIHJlc2lkdWFscy4gV2UgdXNlIGFuIGV4cHJlc3Npb24gc2ltaWxhciB0byB0aGUgb25lIHVzZWQgZm9yIElEVyBhbmQgJGskLXBvaW50IG1lYW5zIGluIENoYXB0ZXIgXEByZWZ7c3BhdGlhbGx5LWNvbnRpbnVvdXMtZGF0YS1pfSAod2Ugd2lsbCB1c2UgJFxsYW1iZGEkIGZvciB0aGUgd2VpZ2h0cyB0byBhdm9pZCBjb25mdXNpbmcgdGhlIHRoZSB3ZWlnaHRzIGluIHZhcmlvZ3JhcGhpYyBhbmFseXNpcyk6DQoNCiQkDQpcaGF0e1xlcHNpbG9ufV9wID0gXHN1bV97aT0xfV5uIHtcbGFtYmRhX3twaX1cZXBzaWxvbl9pfQ0KJCQNCg0KVGhhdCBpcywgJFxoYXR7XGVwc2lsb259X3AkIGlzIGEgbGluZWFyIGNvbWJpbmF0aW9uIG9mIHRoZSBwcmVkaWN0aW9uIHJlc2lkdWFscyBmcm9tIHRoZSB0cmVuZDoNCiQkDQpcZXBzaWxvbl9pID0gel9pIC0gXGhhdHtmfSh4X2ksIHlfaSkNCiQkDQoNCkl0IGlzIHBvc3NpYmxlIHRvIGRlZmluZSB0aGUgZm9sbG93aW5nIF9leHBlY3RlZCBtZWFuIHNxdWFyZWQgZXJyb3JfLCBvciBfcHJlZGljdGlvbiB2YXJpYW5jZV86DQokJA0KXHNpZ21hX3tcZXBzaWxvbn1eMiA9IEVbKFxoYXR7XGVwc2lsb259X3AgLSBcZXBzaWxvbl9pKV4yXQ0KJCQNCg0KVGhlIHByZWRpY3Rpb24gdmFyaWFuY2UgbWVhc3VyZXMgaG93IGNsb3NlLCBvbiBhdmVyYWdlLCB0aGUgcHJlZGljdGlvbiBlcnJvciBpcyB0byB0aGUgcmVzaWR1YWxzLg0KDQpUaGUgcHJlZGljdGlvbiB2YXJpYW5jZSBjYW4gYmUgZGVjb21wb3NlZCBhcyBmb2xsb3dzOg0KJCQNClxzaWdtYV97XGVwc2lsb259XjIgPSBFW1xoYXR7XGVwc2lsb259X3BdICsgRVtcZXBzaWxvbl9pXSAtIDJFW1xoYXR7XGVwc2lsb25faVxlcHNpbG9ufV9wXQ0KJCQNCg0KSXQgdHVybnMgb3V0ICh3ZSB3aWxsIG5vdCBzaG93IGRlIGRldGFpbGVkIGRlcml2YXRpb24sIGJ1dCBpdCBjYW4gYmUgY29uc3VsdGVkIFtoZXJlXShodHRwczovL21zdS5lZHUvfmFzaHRvbi9jbGFzc2VzLzg2Ni9wYXBlcnMvZ2F0cmVsbF9vcmRrcmlnZS5wZGYpKSwgdGhhdCB0aGUgZXhwcmVzaW9uIGZvciB0aGUgcHJlZGljdGlvbiB2YXJpYW5jZSBkZXBlbmRzIG9uIHRoZSB3ZWlnaHRzOg0KJCQNClxzaWdtYV97XGVwc2lsb259XjIgPSBcc3VtX3tpPTF9Xm4gXHN1bV97aj0xfV5ue1xsYW1iZGFfe2lwfVxsYW1iZGFfe2pwfUNfe2lqfX0gKyBcc2lnbWFeMiArIDJcc3VtX3tpPTF9XntufXtcbGFtYmRhX3tpcH1DX3tpcH19DQokJA0Kd2hlcmUgJENfe2lqfSQgaXMgdGhlIGF1dG9jb3ZhcmlhbmNlIGJldHdlZW4gb2JzZXJ2YXRpb25zIGF0ICRpJCBhbmQgJGokLCBhbmQgJENfe2lwfSQgaXMgdGhlIGF1dG9jb3ZhcmlhbmNlIGJldHdlZW4gdGhlIG9ic2VydmF0aW9uIGF0ICRpJCBhbmQgcHJlZGljdGlvbiBsb2NhdGlvbiAkcCQuDQoNCkZvcnR1bmF0ZWx5IGZvciB1cywgdGhlIHNlbWl2YXJpb2dyYW0gYW5kIHRoZSBhdXRvY292YXJpYW5jZSBpcyBzdHJhaWdodGZvcndhcmQ6DQokJA0KQ197en0oaCkgPVxzaWdtYV4yIC0gXGhhdHtcZ2FtbWF9X3t6fShoKQ0KJCQNCg0KVGhpcyBtZWFucyB0aGF0LCBnaXZlbiB0aGUgZGlzdGFuY2UgJGgkIGJldHdlZW4gJGkkIGFuZCAkaiQsIGFuZCAkaSQgYW5kICRwJCwgd2UgY2FuIHVzZSBhIHNlbWl2YXJpb2dyYW0gdG8gb2J0YWluIHRoZSBhdXRvY292YXJpYW5jZXMgbmVlZGVkIHRvIGNhbGN1bGF0ZSB0aGUgcHJlZGljdGlvbiB2YXJpYW5jZS4gV2UgYXJlIHN0aWxsIG1pc3NpbmcsIGhvd2V2ZXIsIHRoZSB3ZWlnaHRzICRcbGFtYmRhJCwgd2hpY2ggYXJlIG5vdCBrbm93biBhIHByaW9yaS4NCg0KVGhlc2Ugd2VpZ2h0cyBjYW4gYmUgb2J0YWluZWQgaWYgd2UgdXNlIHRoZSBmb2xsb3dpbmcgcnVsZXM6DQoNCj4gVGhlIGV4cGVjdGF0aW9uIG9mIHRoZSBwcmVkaWN0aW9uIGVycm9ycyBpcyB6ZXJvICh1bmJpYXNzZWRuZXNzKQ0KPiBGaW5kIHRoZSB3ZWlnaHRzICRsYW1iZGEkIHRoYXQgbWluaW1pemUgdGhlIHByZWRpY3Rpb24gdmFyaWFuY2UgKG9wdGltYWwgZXN0aW1hdG9yKS4NCg0KVGhpcyBtYWtlcyBzZW5zZSwgc2luY2Ugd2Ugd291bGQgbGlrZSBvdXIgcHJlZGljdGlvbnMgdG8gYmUgdW5iaWFzZWQgKGkuZS4sIGFjY3VyYXRlKSBhbmQgYXMgcHJlY2lzZSBhcyBwb3NzaWJsZSwgdGhhdCBpcywgdG8gaGF2ZSB0aGUgc21hbGxlc3QgdmFyaWFuY2UgKHJlY2FsbCB0aGUgZGlzY3Vzc2lvbiBhYm91dCBhY2N1cmFjeSBhbmQgcHJlY2lzaW9uIGluIENoYXB0ZXIgXEByZWZ7c3BhdGlhbGx5LWNvbnRpbnVvdXMtZGF0YS1paWl9KS4NCg0KQWdhaW4sIHNvbHZpbmcgdGhlIG1pbmltaXphdGlvbiBwcm9ibGVtIGlzIGJleW9uZCB0aGUgc2NvcGUgb2Ygb3VyIHByZXNlbnRhdGlvbiwgYnV0IGl0IHN1ZmZpY2VzIHRvIHNheSB0aGF0IHRoZSByZXN1bHQgaXMgYXMgZm9sbG93czoNCg0KJCQNClxtYXRoYmZ7XGxhbWJkYX1fcCA9IFxtYXRoYmZ7Q31eey0xfVxtYXRoaXR7Y31fe3B9DQokJA0KDQp3aGVyZSAkXG1hdGhiZntDfSQgaXMgdGhlIGNvdmFyaWFuY2UgbWF0cml4LCBhbmQgJFxtYXRoaXR7Y31fe3B9JCBpcyB0aGUgY292YXJpYW5jZSB2ZWN0b3IgZm9yIGxvY2F0aW9uICRwJC4NCg0KSW4gc3VtbWFyeSwga3JpZ2luZyBpcyBhIG1ldGhvZCB0byBvcHRpbWFsbHkgZXN0aW1hdGUgdGhlIHZhbHVlIG9mIGEgdmFyaWFibGUgYXQgJHAkIGFzIGEgd2VpZ2h0ZWQgc3VtIG9mIHRoZSBvYnNlcnZhdGlvbnMgb2YgdGhlIHNhbWUgdmFyaWFibGUgYXQgbG9jYXRpb25zICRpJC4gVGhpcyBtZXRob2QgaXMga25vd24gdG8gaGF2ZSB0aGUgcHJvcGVydGllcyBvZiAqKkIqKmVzdCAoaW4gdGhlIHNlbnNlIHRoYXQgaXQgbWluaW1pemVzIHRoZSB2YXJpYW5jZSkgKipMKippbmVhciAoYmVjYXVzZSBwcmVkaWN0aW9ucyBhcmUgYSBsaW5lYXIgY29tYmluYXRpb24gb2Ygd2VpZ2h0cykgKipVKipuYmlhc2VkIChzaW5jZSB0aGUgZXN0aW1hdG9ycyBvZiB0aGUgcHJlZGljdGlvbiBlcnJvcnMgYXJlIHplcm8pICoqUCoqcmVkaWN0b3IsIG9yICoqQkxVUCoqLg0KDQpLcmlnaW5nIGlzIGltcGxlbWVudGVkIGluIHRoZSBwYWNrYWdlIGBnc3RhdGAgYXMgZm9sbG93cy4NCg0KVG8gcHV0IGtyaWdpbmcgdG8gd29yayB3ZSBtdXN0IGZpcnN0IGNvbmR1Y3QgdmFyaW9ncmFwaGljIGFuYWx5c2lzIG9mIHRoZSByZXNpZHVhbHMuIFRoZSBmdW5jdGlvbiBgdmFyaW9ncmFtYCB1c2VzIGFzIGFuIGFyZ3VtZW50IGEgc2ltcGxlIGZlYXR1cmVzIG9iamVjdCB0aGF0IHdlIGNhbiBjcmVhdGUgYXMgZm9sbG93czoNCmBgYHtyfQ0KV2Fsa2VyX0xha2Uuc2YgPC0gV2Fsa2VyX0xha2UgJT4lDQogIHN0X2FzX3NmKGNvb3JkcyA9IGMoIlgiLCAiWSIpLA0KICAgICAgICAgICByZW1vdmUgPSBGQUxTRSkgIyBSZW1vdmUgc2V0IHRvIGZhbHNlIHRvIHJldGFpbiB0aGUgWCBhbmQgWSBjb29yZGluYXRlcyBpbiB0aGUgZGF0YWZyYW1lIGFmdGVyIHRoZXkgYXJlIGNvbnZlcnRlZCB0byBzaW1wbGUgZmVhdHVyZXMNCmBgYA0KDQpUaGUgdmFyaW9ncmFtIG9mIHRoZSByZXNpZHVhbHMgY2FuIGJlIG9idGFpbmVkIGJ5IHNwZWNpZnlpbmcgYSB0cmVuZCBzdXJmYWNlIGluIHRoZSBmb3JtdWxhOg0KYGBge3J9DQp2YXJpb2dyYW1fdiA8LSB2YXJpb2dyYW0oViB+IFgzICsgWDJZICsgWDIgKyBYICsgWFkgKyBZICsgWTIgKyBYWTIgKyBZMywgDQogICAgICAgICAgICAgICAgICAgICAgICAgZGF0YSA9IFdhbGtlcl9MYWtlLnNmKQ0KZ2dwbG90KGRhdGEgPSB2YXJpb2dyYW1fdiwgYWVzKHggPSBkaXN0LCB5ID0gZ2FtbWEpKSArDQogIGdlb21fcG9pbnQoKSArIA0KICBnZW9tX3RleHQoYWVzKGxhYmVsID0gbnApLCBudWRnZV95ID0gLTE1MDApICsgIyBOdWRnZSB0aGUgbGFiZWxzIGF3YXkgZnJvbSB0aGUgcG9pbnRzDQogIHhsYWIoIkRpc3RhbmNlIikgKyB5bGFiKCJTZW1pdmFyaWFuY2UiKQ0KYGBgDQoNCllvdSBjYW4gdmVyaWZ5IHRoYXQgdGhlIHNlbWl2YXJpb2dyYW0gYWJvdmUgY29ycmVzcG9uZHMgdG8gdGhlIHJlc2lkdWFscyBieSByZXBlYXRpbmcgdGhlIGFuYWx5c2lzIGRpcmVjdGx5IG9uIHRoZSByZXNpZHVhbHMuIEZpcnN0IGpvaW4gdGhlIHJlc2lkdWFscyB0byB0aGUgYFNwYXRpYWxQb2ludHNEYXRhRnJhbWVgOg0KYGBge3J9DQpXYWxrZXJfTGFrZS5zZiRlIDwtIFdMLnRyZW5kMyRyZXNpZHVhbHMNCmBgYA0KDQpBbmQgdGhlbiBjYWxjdWxhdGUgdGhlIHNlbWl2YXJpb2dyYW0gYW5kIHBsb3Q6DQpgYGB7cn0NCnZhcmlvZ3JhbV9lIDwtIHZhcmlvZ3JhbShlIH4gMSwgDQogICAgICAgICAgICAgICAgICAgICAgICAgZGF0YSA9IFdhbGtlcl9MYWtlLnNmKQ0KZ2dwbG90KGRhdGEgPSB2YXJpb2dyYW1fZSwgYWVzKHggPSBkaXN0LCB5ID0gZ2FtbWEpKSArDQogIGdlb21fcG9pbnQoKSArIA0KICBnZW9tX3RleHQoYWVzKGxhYmVsID0gbnApLCBudWRnZV95ID0gLTE1MDApICsNCiAgeGxhYigiRGlzdGFuY2UiKSArIHlsYWIoIlNlbWl2YXJpYW5jZSIpDQpgYGANCg0KVGhlIGVtcGlyaWNhbCBzZW1pdmFyaW9ncmFtIGlzIHVzZWQgdG8gZXN0aW1hdGUgYSBzZW1pdmFyaW9ncmFtIGZ1bmN0aW9uOg0KYGBge3J9DQp2YXJpb2dyYW1fdi50IDwtIGZpdC52YXJpb2dyYW0odmFyaW9ncmFtX3YsIG1vZGVsID0gdmdtKCJFeHAiLCAiU3BoIiwgIkdhdSIpKQ0KdmFyaW9ncmFtX3YudA0KYGBgDQoNClRoZSB2YXJpb2dyYW0gZnVuY3Rpb24gcGxvdHMgYXMgZm9sbG93czoNCmBgYHtyfQ0KZ2FtbWEudCA8LSB2YXJpb2dyYW1MaW5lKHZhcmlvZ3JhbV92LnQsIG1heGRpc3QgPSAxMzApDQpnZ3Bsb3QoZGF0YSA9IHZhcmlvZ3JhbV92LCBhZXMoeCA9IGRpc3QsIHkgPSBnYW1tYSkpICsNCiAgZ2VvbV9wb2ludChzaXplID0gMykgKyANCiAgZ2VvbV9saW5lKGRhdGEgPSBnYW1tYS50LCBhZXMoeCA9IGRpc3QsIHkgPSBnYW1tYSkpICsNCiAgeGxhYigiRGlzdGFuY2UiKSArIHlsYWIoIlNlbWl2YXJpYW5jZSIpDQpgYGANCg0KV2Ugd2lsbCBjb252ZXJ0IHRoZSBwcmVkaWN0aW9uIGdyaWQgdG8gYSBzaW1wbGUgZmVhdHVyZXMgb2JqZWN0Og0KYGBge3J9DQpkZi5zZiA8LSBkZi5wICU+JQ0KICBzdF9hc19zZihjb29yZHMgPSBjKCJYIiwgIlkiKSwNCiAgICAgICAgICAgcmVtb3ZlID0gRkFMU0UpDQpgYGANCg0KVGhlbiwgd2UgY2FuIGtyaWdlIHRoZSBmaWVsZCBhcyBmb2xsb3dzIChlbnN1cmUgdGhhdCBwYWNrYWdlcyBgc2ZgIGFuZCBgc3RhcnNgIGFyZSBpbnN0YWxsZWQpOg0KYGBge3J9DQpWLmtyaWdlZCA8LSBrcmlnZShWIH4gWDMgKyBYMlkgKyBYMiArIFggKyBYWSArIFkgKyBZMiArIFhZMiArIFkzLA0KICAgICAgICAgICAgICBXYWxrZXJfTGFrZS5zZiwgZGYuc2YsIHZhcmlvZ3JhbV92LnQpDQpgYGANCg0KRXh0cmFjdCB0aGUgcHJlZGljdGlvbnMgYW5kIHByZWRpY3Rpb24gdmFyaWFuY2UgZnJvbSB0aGUgb2JqZWN0IGBWLmtyaWdlZGA6DQpgYGB7cn0NClYua20gPC0gbWF0cml4KGRhdGEgPSBWLmtyaWdlZCR2YXIxLnByZWQsDQogICAgICAgICAgICAgICBucm93ID0gMTE5LCBuY29sID0gMTAzLCBieXJvdyA9IFRSVUUpDQpWLnNtIDwtIG1hdHJpeChkYXRhID0gVi5rcmlnZWQkdmFyMS52YXIsDQogICAgICAgICAgICAgICBucm93ID0gMTE5LCBuY29sID0gMTAzLCBieXJvdyA9IFRSVUUpDQpgYGANCg0KV2UgY2FuIG5vdyBwbG90IHRoZSBpbnRlcnBvbGF0ZWQgZmllbGQ6DQpgYGB7cn0NClYua20ucGxvdCA8LSBwbG90X2x5KHggPSB+WC5wLCB5ID0gflkucCwgeiA9IH5WLmttLCANCiAgICAgICAgdHlwZSA9ICJzdXJmYWNlIiwgY29sb3JzID0gIllsT3JSZCIpICU+JSANCiAgbGF5b3V0KHNjZW5lID0gbGlzdCgNCiAgICBhc3BlY3Rtb2RlID0gIm1hbnVhbCIsIGFzcGVjdHJhdGlvID0gbGlzdCh4ID0gMSwgeSA9IDEsIHogPSAxKSkpDQpWLmttLnBsb3QNCmBgYA0KDQpBbHNvLCB3ZSBjYW4gcGxvdCB0aGUga3JpZ2luZyBzdGFuZGFyZCBlcnJvcnMgKHRoZSBzcXVhcmUgcm9vdCBvZiB0aGUgcHJlZGljdGlvbiB2YXJpYW5jZSkuIFRoaXMgZ2l2ZXMgYW4gZXN0aW1hdGUgb2YgdGhlIHVuY2VydGFpbnR5IGluIHRoZSBwcmVkaWN0aW9uczoNCmBgYHtyfQ0KVi5zbS5wbG90IDwtIHBsb3RfbHkoeCA9IH5YLnAsIHkgPSB+WS5wLCB6ID0gfnNxcnQoVi5zbSksIA0KICAgICAgICB0eXBlID0gInN1cmZhY2UiLCBjb2xvcnMgPSAiWWxPclJkIikgJT4lIA0KICBsYXlvdXQoc2NlbmUgPSBsaXN0KA0KICAgIGFzcGVjdG1vZGUgPSAibWFudWFsIiwgYXNwZWN0cmF0aW8gPSBsaXN0KHggPSAxLCB5ID0gMSwgeiA9IDEpKSkNClYuc20ucGxvdA0KYGBgDQoNCldoZXJlIGFyZSBwcmVkaWN0aW9ucyBtb3JlL2xlc3MgcHJlY2lzZT8=